﻿//https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k)
    {
        int n = nums.size();
        int m = 0;
        int minnums = INT_MAX;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] < 0) m++;
            minnums = min(minnums, abs(nums[i]));
        }

        sort(nums.begin(), nums.end());
        int ret = 0;
        if (m > k)
        {
            for (int i = 0; i < k; i++)
            {
                ret += (-nums[i]);
            }
            for (int i = k; i < n; i++)
            {
                ret += nums[i];
            }
        }
        else
        {
            for (int i = 0; i < n; i++)
                ret += abs(nums[i]);
            if ((k - m) % 2 != 0)
                ret -= 2 * minnums;
        }

        return ret;


    }
};
